活动网(AOV、AOE)——数据结构系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

AOV 网（Activity On Vertex，顶点表示活动的网）和 AOE 网（Activity On Edge，边表示活动的网）是带权有向无环图（DAG）的两大核心应用：

AOV 网：用顶点表示活动、有向边表示活动间的先后依赖关系（如项目流程、课程选修顺序），核心求解拓扑排序—— 得到满足所有依赖关系的活动执行顺序；
AOE 网：用边表示活动、顶点表示事件（活动的开始 / 结束节点）、边权表示活动持续时间，核心求解关键路径—— 从源点（开始事件）到汇点（结束事件）的最长路径，路径上的活动为关键活动，决定项目的最短完成时间。

两者均要求图为有向无环图（DAG），若存在环则无拓扑排序（活动间循环依赖），也无关键路径（项目无法完成）。

图结构的实现方式：

邻接矩阵图：是一种使用「一维数组 + 二维数组」存储顶点和边数据的图结构，稠密图中常被采用；
邻接链表图：是一种使用「数组 + 链表」存储顶点和边数据的图结构，稀疏图中常被采用；

学习经典应用场景前，请根据上面的教程封装好自定义图，所有场景实例直接复用

教程目录导航

▼

连通性问题

一、AOV 网与拓扑排序

1.1 AOV 网基本概念

AOV 网解决“先做什么，后做什么”（顺序问题）

顶点：代表活动（如 “完成需求分析”“编写代码”）；
有向边：表示活动u完成后，活动v才能开始（u是v的前驱活动，v是u的后继活动）；
入度：顶点v的入度表示v的未完成前驱活动数（入度为 0 的顶点无前置依赖，可直接执行）；
核心约束：无环（否则出现 “活动 A 依赖 B，B 依赖 A” 的循环，流程无法推进）。

1.2 拓扑排序定义

对 AOV 网的顶点进行线性排序，满足：若图中存在有向边，则排序中u一定在v之前。

一个 DAG 的拓扑排序不唯一（多个入度为 0 的顶点时，可任选其一）；
若排序结果包含所有顶点，说明网无环；否则存在环，为无效 AOV 网。

1.3 拓扑排序经典算法：Kahn 算法（入度表 + 队列）

最易理解、易实现的拓扑排序算法，核心是反复删除入度为 0 的顶点，并更新其邻接顶点的入度，步骤如下：

初始化：
1. 计算所有顶点的入度，存入入度数组inDegree[]；
2. 初始化队列，将所有入度为 0的顶点入队（初始可执行的活动）；
3. 定义结果数组topoOrder[]，存储拓扑排序结果。
迭代处理：
1. 若队列为空，终止循环；
2. 出队顶点u，将其加入topoOrder[]；
3. 遍历u的所有邻接顶点v：
  - 将v的入度减 1（u完成，v的一个前驱依赖消除）；
  - 若v的入度变为 0，将v入队（v的所有前驱完成，可执行）。
有效性判断：
1. 若topoOrder[]的长度等于顶点总数，拓扑排序成功（无环）；
2. 否则，图中存在环，拓扑排序失败（无效 AOV 网）。


#include <iostream>
#include <vector>
#include <queue>
#include"LinkedGraph.h"

using namespace std;

// 打印拓扑序列（支持顶点名称映射）
void printKahnSort(const LinkedGraph& adj, vector<int>& topoOrder) {
    int n = topoOrder.size();
    if (n != adj.vertexNum) {
        cout << "无有效拓扑序列！" << endl;
        return;
    }
    cout << "Kahn算法求拓扑序列：";
    for(int i=0;i < n;i++)
    {
        cout << adj.adjList[topoOrder[i]].data;
        if(i != n-1)
        {
            cout << "->";
        }
    }
    cout << endl;
}

// 拓扑排序：Kahn算法
// adj-邻接表，topoOrder-输出拓扑序列
// 返回值：true-排序成功（无环），false-排序失败（有环）
bool kahnSort(const LinkedGraph& adj, vector<int>& topoOrder) {
    int n = adj.vertexNum;// 顶点数
    vector<int> inDegree(n, 0);// 入度数组
    queue<int> q;

    // 计算所有顶点的入度，存入入度数组inDegree[]；
    for (int u = 0; u < n; ++u) {
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            inDegree[edge->adjvex]++;
            edge = edge->next;
        }
        delete edge;
    }

    // 初始化队列，将所有入度为 0的顶点入队（初始可执行的活动）；
    for (int i = 0; i < adj.vertexNum; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 迭代处理：
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);  // 出队顶点u，将其加入topoOrder[]；

        // 遍历u的所有邻接顶点，更新入度
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            int v = edge->adjvex;
            inDegree[v]--;// 将v的入度减 1（u完成，v的一个前驱依赖消除）；
            if (inDegree[v] == 0) {
                q.push(v);// 若v的入度变为 0，将v入队（v的所有前驱完成，可执行）。
            }
            edge = edge->next;
        }
        delete edge;
    }

    // 拓扑序列长度等于顶点数，说明无环，排序成功
    return topoOrder.size() == n;
}

// 测试案例
int main() {
    LinkedGraph graph;
    vector<int> topoOrder;// 拓扑序列

    // 1. 添加顶点（A、B、C、D、E）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');

    // 2. 添加边（无权有向图）
    graph.addDirectedEdge('A','B',1);
    graph.addDirectedEdge('A','C',1);
    graph.addDirectedEdge('A','D',1);

    graph.addDirectedEdge('B','E',1);
    graph.addDirectedEdge('C','E',1);
    graph.addDirectedEdge('D','E',1);    

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 求拓扑序列
    kahnSort(graph, topoOrder);

    // 5. 打印拓扑序列
    printKahnSort(graph, topoOrder);

    return 0;
}

输出结果


===== 邻接表（带权）=====
A -> (D, 1) (C, 1) (B, 1)
B -> (E, 1)
C -> (E, 1)
D -> (E, 1)
E ->
Kahn算法求拓扑序列：A->D->C->B->E

二、AOE 网与关键路径

1.1 AOV 网基本概念

AOE 网解决“最快多久完成，哪些活动不能延迟”（时间优化问题）；

AOE 网是带权有向无环图（DAG），是 AOV 网的扩展（关注活动时间和项目工期），核心概念：

顶点：代表事件（如 “所有前置活动完成”“项目开始 / 结束”），事件仅表示状态，无持续时间；
有向边：代表活动，边权w表示该活动的持续时间；
源点：唯一的入度为 0的顶点（项目开始事件，记为v0）；
汇点：唯一的出度为 0的顶点（项目结束事件，记为vn）；
活动的最早开始时间：该活动对应边的起点事件的最早发生时间；
活动的最晚开始时间：该活动对应边的终点事件的最晚发生时间 - 活动持续时间；
关键活动：最早开始时间 = 最晚开始时间的活动（无时间余量，延迟则整个项目工期延迟）；
关键路径：从源点到汇点，由所有关键活动组成的最长路径（路径总权值为项目最短完成时间，因关键活动无余量，必须按最长路径执行）。

1.2 关键路径求解核心：4 个关键数组

设顶点数为n，顶点编号0∼n−1，源点为0，汇点为n−1，定义 4 个核心数组（基础版基于邻接表实现）：

ve[]（Vertex Early）：顶点i的最早发生时间—— 从源点到i的最长路径权值（只有所有前驱活动完成，事件i才能发生，故取最长路径，保证所有前驱完成）；
vl[]（Vertex Late）：顶点i的最晚发生时间—— 在不推迟项目工期的前提下，事件i的最晚发生时间（等于汇点的最早发生时间ve[n−1]，反向推导）；
e[]（Activity Early）：活动k的最早开始时间—— 活动k对应边，则e[k]=ve[u]（起点事件最早发生，活动即可开始）；
l[]（Activity Late）：活动k的最晚开始时间—— 活动k对应边，权值为w，则l[k]=vl[v]−w（终点事件最晚发生前，活动必须完成）。

1.3 关键路径求解步骤（基于拓扑排序）

关键路径依赖拓扑排序（保证正向推导ve[]时，前驱顶点已处理）和逆拓扑排序（保证反向推导vl[]时，后继顶点已处理），核心分 3 步：

步骤 1：正向拓扑排序，计算ve[]
1. 初始化：ve[0∼n−1]=0（所有事件最早发生时间初始为 0）；
2. 按拓扑排序顺序遍历每个顶点u：
  - 遍历u的所有邻接顶点v，对应边权为w：
  - 若ve[v] < ve[u]+w，则ve[v]=ve[u]+w（取最长路径，保证所有前驱活动完成）；
3. 最终，汇点的ve[n−1]即为项目最短完成时间。
步骤 2：反向逆拓扑排序，计算vl[]
1. 初始化：vl[0∼n−1]=ve[n−1]（所有事件最晚发生时间初始为项目工期，汇点的vl=ve）；
2. 按逆拓扑排序顺序（拓扑排序结果的倒序）遍历每个顶点v：
  - 遍历v的所有前驱顶点u（或遍历邻接表的反向边），对应边权为w：
  - 若vl[u]>vl[v]−w，则vl[u]=vl[v]−w（取最小值，保证不推迟项目工期）。
步骤 3：遍历所有活动，筛选关键活动
1. 对每个活动k（对应边
  ，权值w）：
  - 计算e[k]=ve[u]，l[k]=vl[v]−w；
  - 若e[k]=l[k]，则该活动为关键活动；
2. 否则，图中存在环，拓扑排序失败（无效 AOV 网）。


#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include"LinkedGraph.h"

using namespace std;

bool isBuilt;              // 标记图是否已构建
int source;                // 源点（入度0）
int sink;                  // 汇点（出度0）
int vertexNum;             // 顶点数（事件数）

// 检查AOE网合法性：必须是DAG、仅有一个源点、仅有一个汇点
bool checkValid(const LinkedGraph& adj, const vector<int> inDegree, const vector<int>& topoOrder) {
    if (topoOrder.empty()) {
        cerr << "错误：AOE网存在环，不合法！" << endl;
        return false;
    }
    // 找源点（入度0）
    vector<int> sourceList;
    for (int i = 0; i < vertexNum; i++) {
        if (inDegree[i] == 0) sourceList.push_back(i);
    }
    // 找汇点（出度0）
    vector<int> sinkList;
    for (int i = 0; i < vertexNum; i++) {
        if (adj.adjList[i].firstedge == nullptr) sinkList.push_back(i);
    }
    if (sourceList.size() != 1) {
        cerr << "错误：AOE网需仅有一个源点，当前找到" << sourceList.size() << "个！" << endl;
        return false;
    }
    if (sinkList.size() != 1) {
        cerr << "错误：AOE网需仅有一个汇点，当前找到" << sinkList.size() << "个！" << endl;
        return false;
    }
    source = sourceList[0];
    sink = sinkList[0];
    return true;
}

// 查找从start到end的所有路径
void dfsFindPath(const vector<vector<int>>& adj, int start, int end,
                 vector<int>& path, vector<vector<int>>& res) {
    path.push_back(start);
    if (start == end) {
        res.push_back(path);
        path.pop_back();
        return;
    }
    for (int v : adj[start]) {
        dfsFindPath(adj, v, end, path, res);
    }
    path.pop_back();
}

// 打印关键路径（由关键活动组成，从源点到汇点）
void printCriticalPath(const vector<pair<int, int>>& criticalAct) {
    if (criticalAct.empty() || source == -1 || sink == -1) {
        cout << "无有效关键路径！" << endl;
        return;
    }
    // 构建关键活动的邻接表
    vector<vector<int>> cpAdj(vertexNum);
    for (const auto& p : criticalAct) {
        cpAdj[p.first].push_back(p.second);
    }
    // 深度优先搜索（DFS）查找从源点到汇点的关键路径
    vector<int> path;
    vector<vector<int>> allCriticalPaths;
    dfsFindPath(cpAdj, source, sink, path, allCriticalPaths);

    // 输出所有关键路径
    cout << "AOE网所有关键路径（从源点" << source << "到汇点" << sink << "）：" << endl;
    for (size_t i = 0; i < allCriticalPaths.size(); i++) {
        cout << "  路径" << i+1 << "：";
        for (int v : allCriticalPaths[i]) {
            cout << adj.adjList[v].data;
            if (v != sink) cout << " -> ";
        }
        cout << endl;
    }
}

// 求关键路径：返回关键活动（pair<u,v>），输出工程最短时间、ve、vl、关键活动
vector<pair<int, int>> criticalPath(const LinkedGraph& adj, int& minProjectTime,vector<int>& topoOrder) {
    vector<pair<int, int>> criticalActivities; // 存储关键活动<u,v>
    vector<int> inDegree(vertexNum, 0);// 入度数组
    minProjectTime = 0;
    if (!isBuilt || vertexNum == 0) {
        cerr << "错误：AOE网未构建或无顶点！" << endl;
        return criticalActivities;
    }

    // 计算所有顶点的入度，存入入度数组inDegree[]；
    for (int u = 0; u < vertexNum; ++u) {
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            inDegree[edge->adjvex]++;
            edge = edge->next;
        }
        delete edge;
    }

    // 步骤1：检查AOE网合法性
    if (!checkValid(adj, inDegree, topoOrder)) {
        return criticalActivities;
    }

    // 步骤2：求事件最早发生时间ve[]
    vector<int> ve(vertexNum, INT_MIN);
    ve[source] = 0; // 源点最早发生时间为0
    for (int u : topoOrder) { // 按拓扑顺序遍历
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            int v = edge->adjvex;
            int w = edge->weight;
            if (ve[v] < ve[u] + w) {
                ve[v] = ve[u] + w;
            }
            edge = edge->next;
        }
        delete edge;
    }
    minProjectTime = ve[sink]; // 汇点的ve就是工程最短完成时间

    // 步骤3：求事件最迟发生时间vl[]
    vector<int> vl(vertexNum, INT_MAX);
    vl[sink] = ve[sink]; // 汇点最迟发生时间=最早发生时间
    // 按逆拓扑顺序遍历（反转拓扑序列）
    reverse(topoOrder.begin(), topoOrder.end());
    for (int u : topoOrder) {
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            int v = edge->adjvex;
            int w = edge->weight;
            if (vl[u] > vl[v] - w) {
                vl[u] = vl[v] - w;
            }
            edge = edge->next;
        }
        delete edge;
    }

    // 步骤4：遍历所有边，计算松驰时间，找关键活动（slack=0）
    cout << "\n===== AOE网关键路径分析 =====" << endl;
    cout << "事件最早发生时间ve[]：";
    for (int x : ve) cout << x << " ";
    cout << "\n事件最迟发生时间vl[]：";
    for (int x : vl) cout << x << " ";
    cout << "\n工程最短完成时间：" << minProjectTime << endl;
    cout << "所有活动分析（u->v, 时间w, 最早开始时间, 最迟开始时间, 松驰时间）：" << endl;

    for (int u = 0; u < vertexNum; u++) {
        EdgeNode* edge = adj.adjList[u].firstedge;
        while(edge != nullptr)
        {
            int v = edge->adjvex;
            int w = edge->weight;
            int e_activity = ve[u];          // 活动最早开始时间
            int l_activity = vl[v] - w;      // 活动最迟开始时间
            int slack = l_activity - e_activity; // 松驰时间
            cout << "  " << adj.adjList[u].data << "->" << adj.adjList[v].data << ", " << w << ", "
                 << e_activity << ", " << l_activity << ", " << slack << endl;
            // 松驰时间为0，是关键活动
            if (slack == 0) {
                criticalActivities.emplace_back(u, v);
            }
            edge = edge->next;
        }
        delete edge;
    }

    // 输出关键活动
    if (!criticalActivities.empty()) {
        cout << "关键活动（slack=0）：";
        for (size_t i = 0; i < criticalActivities.size(); i++) {
            int u = criticalActivities[i].first;
            int v = criticalActivities[i].second;
            cout << adj.adjList[u].data << "->" << adj.adjList[v].data;
            if (i != criticalActivities.size() - 1) cout << ", ";
        }
        cout << endl;
    } else {
        cerr << "错误：未找到关键活动！" << endl;
    }

    return criticalActivities;
}


// 测试案例
int main() {
    LinkedGraph graph;
    vector<int> topoOrder;//拓扑序列
    int minProjectTime=0;

    // 1. 添加顶点（A、B、C、D、E、F、G、H）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');
    graph.addVertex('G');
    graph.addVertex('H');

    vertexNum = graph.vertexNum;
    vector<int> inDegree(vertexNum, 0);// 入度数组

    // 2. 添加边（带权有向图）
    graph.addDirectedEdge('A','B',7);
    graph.addDirectedEdge('A','C',6);

    graph.addDirectedEdge('B','E',4);

    graph.addDirectedEdge('C','D',3);
    graph.addDirectedEdge('C','E',5);

    graph.addDirectedEdge('D','F',2);
    graph.addDirectedEdge('D','H',5);

    graph.addDirectedEdge('E','F',3);
    graph.addDirectedEdge('E','G',4);

    graph.addDirectedEdge('F','H',2);

    graph.addDirectedEdge('G','H',4);

    isBuilt = true;

    // 3. 打印邻接矩阵
    graph.printAdjacency();

    // 4. 求拓扑序列
    kahnSort(graph, inDegree, topoOrder);

    // 5. 打印拓扑序列
    printKahnSort(graph, topoOrder);

    // 6. 求关键路径
    vector<pair<int, int>> criticalAct = criticalPath(graph, minProjectTime, topoOrder);

    // 7. 打印关键路径
    printCriticalPath(graph, criticalAct);

    return 0;
}

输出结果


===== 邻接表（带权）=====
A -> (C, 6) (B, 7)
B -> (E, 4)
C -> (E, 5) (D, 3)
D -> (H, 5) (F, 2)
E -> (G, 4) (F, 3)
F -> (H, 2)
G -> (H, 4)
H ->
Kahn算法求拓扑序列：A->C->B->D->E->G->F->H

===== AOE网关键路径分析 =====
事件最早发生时间ve[]：0 7 6 9 11 14 15 19
事件最迟发生时间vl[]：0 7 6 14 11 17 15 19
工程最短完成时间：19
所有活动分析（u->v, 时间w, 最早开始时间, 最迟开始时间, 松驰时间）：
  A->C, 6, 0, 0, 0
  A->B, 7, 0, 0, 0
  B->E, 4, 7, 7, 0
  C->E, 5, 6, 6, 0
  C->D, 3, 6, 11, 5
  D->H, 5, 9, 14, 5
  D->F, 2, 9, 15, 6
  E->G, 4, 11, 11, 0
  E->F, 3, 11, 14, 3
  F->H, 2, 14, 17, 3
  G->H, 4, 15, 15, 0
关键活动（slack=0）：A->C, A->B, B->E, C->E, E->G, G->H
AOE网所有关键路径（从源点0到汇点7）：
  路径1：A -> C -> E -> G -> H
  路径2：A -> B -> E -> G -> H

三、典型应用场景

AOV 网的典型应用

课程选修系统：顶点表示课程，边表示先修关系，拓扑排序确定合理的选修顺序；
编译系统依赖解析：顶点表示源文件，边表示头文件依赖，拓扑排序确定文件的编译顺序；
任务调度系统：顶点表示任务，边表示任务间的依赖关系，拓扑排序确定任务的执行顺序。

AOE 网的典型应用

项目管理（PERT/CPM）：如建筑工程、软件开发项目，顶点表示项目阶段（事件），边表示具体工作（活动），关键路径用于项目工期规划和资源优化；
生产流水线调度：顶点表示工序节点（事件），边表示加工工序（活动），关键路径用于确定流水线的瓶颈工序，优化生产效率；
物流配送规划：顶点表示物流节点（事件），边表示运输环节（活动），关键路径用于确定最快配送时间，优化配送流程。

返回顶部